# 在给定的 m x n 网格
#  grid 中，每个单元格可以有以下三个值之一：
#  值 0 代表空单元格；
#  值 1 代表新鲜橘子；
#  值 2 代表腐烂的橘子。
#  每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
#  返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。
#
#  示例 1：
# 输入：grid = [[2,1,1],[1,1,0],[0,1,1]]
# 输出：4
#
#  示例 2：
# 输入：grid = [[2,1,1],[0,1,1],[1,0,1]]
# 输出：-1
# 解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个方向上。
#
#
#  示例 3：
# 输入：grid = [[0,2]]
# 输出：0
# 解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。
#
#  Related Topics 广度优先搜索 数组 矩阵 👍 833 👎 0
from collections import deque
from typing import List


class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        """

        这些腐烂橘子刚开始是新鲜的，而有一个腐烂橘子(我们令其为超级源点)会在下一秒把这些橘子都变腐烂，而这个腐烂橘子刚开始在的时间是 −1 ，
        那么按照广度优先搜索的算法，下一分钟也就是第 000 分钟的时候，这个腐烂橘子会把它们都变成腐烂橘子，
        然后继续向外拓展，所以其实这些腐烂橘子是同一层的节点。那么在广度优先搜索的时候，我们将这些腐烂橘子都放进队列里进行广度优先搜索即可，
        最后每个新鲜橘子被腐烂的最短时间 dis[x][y] 其实是以这个超级源点的腐烂橘子为起点的广度优先搜索得到的结果。
        """
        directions = [(-1, 0), (1, 0), (0, 1), (0, -1)]

        def validate(i: int, j: int) -> bool:
            return True if 0 <= i < m and 0 <= j < n else False

        def bfs(points: list[(int, int, int)]) -> int:
            depth = 0
            q = deque(points)
            while q:

                x, y, depth = q.popleft()
                for dx, dy in directions:
                    tmp_x, tmp_y = x + dx, y + dy
                    if validate(tmp_x, tmp_y) and grid[tmp_x][tmp_y] == 1:
                        grid[tmp_x][tmp_y] = 2
                        q.append((tmp_x, tmp_y, depth + 1))
            return depth

        m, n, res, bads = len(grid), len(grid[0]), 0, list[(int, int, int)]()

        # 遍历整个grid 遇到腐烂的橘子就记录下它的坐标
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 2:
                    bads.append((i, j, 0))
        res = bfs(bads)
        # 遍历完了再看是否还有新鲜的橘子，有就是不能完全腐烂完
        return -1 if any(1 in row for row in grid) else res


if __name__ == '__main__':
    grid = [[2, 1, 1], [1, 1, 0], [0, 1, 1]]
    grid = [[0, 2]]
    grid = [[2, 1, 1], [1, 1, 1], [0, 1, 2]]
    print(Solution().orangesRotting(grid))
